package 回溯;

import java.util.ArrayList;
import java.util.List;

/**
 * @author tmh
 * @date 2024/9/8 16:35
 * @description
 */
public class T39组合总和 {
    //beginIndex的作用：如果要+1，表示该元素就不能被重复选取了
    //不+1，表示该元素还可以继续被选取
    List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        backTracking(candidates, 0, new ArrayList<>(), target, 0);
        return result;
    }

    public void backTracking(int[] candidates, int beginIndex, List<Integer> list, int target, int sum) {
        //超过target直接返回
        if (sum > target) {
            return;
        }
        //等于的话就直接存到result里面
        if (sum == target) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = beginIndex; i < candidates.length; i++) {
            list.add(candidates[i]);
            sum += candidates[i];
            //这里递归的时候i不用加1，表示当前的数字可以重复选
            backTracking(candidates, i, list, target, sum);
            //回溯
            sum -= candidates[i];
            list.remove(list.size() - 1);
        }
    }
}
